A mobile ad hoc network consists of a set of mobile nodes which are free to move and are interconnected through wireless interfaces. Nodes which are not able to communicate directly, use multihop paths using other intermediate nodes in the network as relays. So, a mobile ad hoc node can act both as a mobile router and a mobile host. In addition, the continuous topology changes, the strong requirements in minimizing battery consumption (in devices which are power constrained) as well as the limited network resources, make the problem of routing in these networks a real challenge. However, their completely distributed nature and their ability to operate without depending upon the deployment of any infrastructure, makes them an ideal component of future mobile computing scenarios. These scenarios include among others emergency situations, battlefield assistance and search and rescue operations. Hence, the interest in mobile ad hoc networks is expected to increase in the future.
Multicast is one of the areas in mobile ad hoc networks which is to play a key role in future wireless networks. Key to this is the fact that most of the application scenarios for mobile ad hoc networks are strongly based on many-to-many interactions and they require a high degree of collaboration among terminals. Many services such as multimedia applications, service discovery and many other bandwidth-avid applications can strongly benefit from the underlying support of efficient multicast communications.
The problem of the efficient distribution of communication traffic from a set of senders to a group of receivers in a datagram network was initially studied by Deering [1]. Several multicast routing protocols like Distance Vector Multicast Routing Protocol (DVMRP) [2], Multicast Open Shortest Path First (MOSPF)[3], Core-Based Trees (CBT) [4] and Protocol-Independent Multicast (PIM) [5] have been proposed for Internet Protocol (IP) multicast routing in fixed networks. However, these protocols are not able to perform well in highly mobile and topology changing scenarios such as ad hoc networks. The main reason is that their forwarding structures are fragile. Thus, the cost in terms of the control overhead which they would require to recompute their multicast trees whenever one of the links in the tree breaks, makes unreasonable their deployment in a mobile ad hoc network.
Several multicast routing solutions specifically designed for ad hoc networks have been proposed in the literature [6]. In general, these protocols can be classified into two groups: tree-based and mesh-based approaches. Tree-based schemes construct a multicast tree from each of the sources to all the receivers. Examples of protocols following this approach are Ad-hoc. Multicast Routing protocol utilizing Increasing id-numberS (AMRISU) [7], Multicast Ad Hoc On-Demand Distance Vector (MAODV) [8], Lightweight Adaptive Multicast (LAM) [9] and Adaptive Demand Driven Multicast Routing (ADMR) [10]. The main advantage of using a tree as the underlying forwarding structure is that the number of forwarding nodes tends to be reduced (although not necessarily optimized). However, a tree is very fragile when there is a high mobility in the network. Mesh-based approaches like On-Demand Multicast Routing Protocol (ODMRP) [11] and Core-Assisted Mesh Protocol (CAMP) [12], by using additional links in their underlying forwarding structure, manage to deal with mobility very efficiently. The main drawback of using a mesh is that, due to the additional paths which are created, duplicated data packets can make an excessive consumption of network resources even if a duplicate detection is used. The usual metrics used in the literature to assess the effectiveness of a multicast ad hoc routing protocol are usually related to the control packet overhead. Previous studies have generally neglected the huge impact that the data overhead may have in the overall performance of a protocol. In fact, if we take into account that data traffic consumes more bandwidth than control traffic, the overhead due to the selection of suboptimal routes may easily become more expensive in terms of bandwidth and energy consumption than the cost of sending a few more control packets.
Data Overhead in Ad Hoc Multicast Routing
The goal of multicast routing protocols in ad hoc networks is finding a set of relay nodes so that data packets sent out by multicast sources can be delivered to multicast receivers. Obviously, the number of those relay nodes is lower than the number of nodes except in the case of flooding. The paths defined by the union of all these nodes may resemble different forwarding structures such as shortest path trees, shared trees, minimal Steiner trees, acyclic meshes, etc. In general, the underlying forwarding structure is protocol-specific because it strongly depends on the path creation process implemented by that particular protocol. We define forwarding nodes as those nodes which are in the path between any source and any receiver. Note that even a source or a receiver can also be a forwarding node. FIG. 1 shows a multicast tree in which we identify forwarding nodes by a double circle. Wider lines represent the forwarding structure induced by the forwarding nodes.
There are two basic approaches to build multicast trees: shortest path trees and shared trees [18]. Given a multicast source s, a shortest path tree is formed by the aggregation of the shortest paths from any receiver r to s. The main advantage of this kind of tree is that each destination receives multicast data through its best route, which usually means that the latency from s to each r is also minimized. However, these trees are not optimal in terms of the overall number of transmissions required or the number of forwarding nodes which are required. So, they do not provide optimal bandwidth consumption.
A second variant are the so-called shared trees. Shared trees try to reduce the cost of the multicast tree by reducing the number of links which are required to connect sources and receivers. This is done by selecting the links in the tree which can be used by a bigger number of receivers. Of course, in the resulting tree, individual paths from sources to receivers might not be optimal. For the particular case of ad hoc networks, other approaches like the use of multicast meshes with redundant links have been proposed in protocols like ODMRP [11] and CAMP [12]. These structures are particularly interesting to deal with mobility of the nodes, but obviously they do not minimize the cost of multicast forwarding.
The problem of finding a minimum cost multicast tree is well-known as the minimum Steiner tree problem. Karp [19] demonstrated that this problem is Nondeterministic Polynomial (NP)-complete even when every link has the same cost, by a transformation from the exact cover by 3-sets. There are some heuristic algorithms to compute minimal Steiner trees. For instance, the Minimal Steiner Tree (MST) algorithm ([20, 21]) provides a 2-approximation, and Zelikovsky [22] proposed an algorithm which obtains an 11/6-approximation. However, given the complexity of computing these kinds of trees in a distributed way, most of the existing multicast routing protocols use shortest path trees, which can be easily computed in polynomial time. For mesh-based forwarding, the multicast mesh is usually computed as the union of various shortest path trees.
However, the problem of minimizing the cost of a multicast tree in an ad hoc network needs to be re-formulated in terms of minimizing the number of data transmissions. Given the broadcast nature of wireless ad hoc networks, a minimum Steiner tree does not minimize the cost of the multicast tree. The cost assignment function used in wired networks is not well-defined for ad hoc networks. That is, by assigning a cost to each link of the graph, existing formulations have implicitly assumed that a given node v, needs k transmissions to send a multicast data packet to k of its neighbors. However, in a broadcast medium, the transmission of a multicast data packet from a given node v to any number of its neighbors can be done with a single data transmission. Thus, in ad hoc networks the minimum cost tree is the one which connects sources and receivers by issuing a minimum number of transmissions.
FIG. 2 shows different multicast trees connecting the source (S) to the set of receivers (R). As it is depicted in FIG. 2(a), the union of the shortest path trees results in 3 forwarding nodes. Thus, number of transmissions is 4, one performed by the multicast source and one for each of the forwarding nodes. Similarly, the number of transmissions for the Steiner tree (see FIG. 2(b)) is also 4. We can see from FIG. 2(b), how the Steiner tree tries to minimize the number of non-terminal nodes (i.e. nodes which are not either senders or receivers) which take part in the tree. These nodes are also known as Steiner nodes. Finally, we see in FIG. 2(c) that the minimal data overhead tree, which takes into account the broadcast medium of the network, is able to cover all the receivers with only 3 transmissions. This shows that the Steiner tree problem fails to provide the minimal cost multicast tree in these networks.
Several protocols have been proposed for multicast routing in mobile ad hoc networks. They can be classified into tree or mesh-based depending upon the underlying forwarding structure that they use. Tree-based schemes [7-10, 13] construct a multicast tree from each of the sources to all the receivers using any of the tree computations schemes, discussed in more detail below. Mesh-based approaches [11, 12], compute several paths among senders and destinations. Thus, when the mobility rate increases they are able to tolerate link breaks better than tree-based protocols. Hybrid approaches [14, 15] try to combine the robustness of mesh-based ad hoc routing and the low overhead of tree-based protocols. Finally, there are stateless multicast protocols [16, 17] in which there is no need to maintain a forwarding state on the nodes. For instance, if the nodes to traverse are included in the data packets themselves. The heuristic proposed herein is mainly targeted to mesh-based multicast routing protocols and we therefore focus our discussion on the protocols falling in this category.
ODMRP [11] and CAMP [12] are the best-known mesh-based multicast ad hoc routing protocols. CAMP was designed as an extension of the “Core Based Trees” (CBT [4]) protocol, offering multiple paths, and relieving the core nodes from doing data forwarding. On the other hand, ODMRP introduces the concept of the forwarding group (FG) as the set of intermediate nodes taking part in the multicast mesh. Both of them are able to achieve very high packet delivery ratios, and they both guarantee that the shortest paths are included in the multicast mesh. However, they do not attempt to minimize the data overhead incurred by not selecting minimal cost paths. Most of the works in the literature dealing with the problem of minimizing the costs of multicast trees are related to wired multicast routing. There are many works which propose approximations to Steiner trees. For instance, Jia [27] proposed a distributed heuristic for the Steiner tree problem being able to provide suboptimal multicast trees satisfying certain delay bounds. Waxman [28] also provided two approximation algorithms to the Steiner tree problem in the static case. Chen et al. [29] proposed approximation algorithms to minimize the number of Steiner nodes. However, these proposed approximations are not useful for mobile ad hoc networks because minimal Steiner trees are very fragile to topology changes.
For ad hoc networks, most of the works in the literature devoted to the improvement of multi-point forwarding efficiency for routing protocols have been related to the particular case of flooding (i.e. the broadcast storm problem). Only a few papers study those mechanisms for multicast ad hoc routing. Lim and Kim [30] analyzed the problem of minimal multicast trees in ad hoc networks, but they defined several heuristics based on the minimum connected dominating set (MCDS) which are only valid for flooding. Lee and Kim [31] worked on a solution to reduce the number of forwarding nodes using a probabilistic approach. However, the overhead reductions were lower than the results according to the present invention, discussed below, and their fixed path selection probability makes their proposal unable to perform well under different mobility rates.